
<!DOCTYPE html
  PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<!DOCTYPE html><html xmlns="http://www.w3.org/1999/xhtml">
   <head>
      <meta charset="utf-8"></meta>
      <meta name="viewport" content="width=device-width, initial-scale=1.0"></meta>
      <title>18.3.&nbsp;Centrality Algorithms - Chapter&nbsp;18.&nbsp;Deprecated: Graph Algorithms</title>
      <link rel="stylesheet" type="text/css" href="../../docbook.css"></link>
      <link rel="stylesheet" type="text/css" href="//maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.min.css"></link>
      <link rel="stylesheet" type="text/css" href="//cdn.datatables.net/1.10.13/css/jquery.dataTables.min.css"></link>
      <link rel="stylesheet" type="text/css" href="//cdnjs.cloudflare.com/ajax/libs/font-awesome/4.1.0/css/font-awesome.min.css"></link>
      <link rel="stylesheet" type="text/css" href="//fonts.googleapis.com/css?family=Open+Sans:400,300,400italic,600,300italic"></link>
      <link rel="stylesheet" type="text/css" href="//cdnjs.cloudflare.com/ajax/libs/codemirror/5.11.0/codemirror.min.css"></link>
      <link rel="stylesheet" type="text/css" href="//cdnjs.cloudflare.com/ajax/libs/codemirror/5.11.0/theme/neo.min.css"></link>
      <link rel="stylesheet" type="text/css" href="../../css/chunked-base.css"></link>
      <link rel="stylesheet" type="text/css" href="../../css/extra.css"></link><script src="//code.jquery.com/jquery-1.12.4.js" type="text/javascript"></script><script src="//cdn.datatables.net/1.10.13/js/jquery.dataTables.min.js" type="text/javascript"></script><script src="//maxcdn.bootstrapcdn.com/bootstrap/3.3.6/js/bootstrap.min.js" type="text/javascript"></script><script src="//cdnjs.cloudflare.com/ajax/libs/codemirror/5.11.0/codemirror.min.js" type="text/javascript"></script><script src="//cdnjs.cloudflare.com/ajax/libs/codemirror/5.11.0/addon/runmode/runmode.min.js" type="text/javascript"></script><script src="//cdnjs.cloudflare.com/ajax/libs/codemirror/5.11.0/mode/cypher/cypher.min.js" type="text/javascript"></script><script src="../../javascript/datatable.js" type="text/javascript"></script><script src="../../javascript/colorize.js" type="text/javascript"></script><script src="../../javascript/tabs-for-chunked.js" type="text/javascript"></script><script src="../../javascript/mp-nav.js" type="text/javascript"></script><script src="../../javascript/versionswitcher.js" type="text/javascript"></script><script src="../../javascript/version.js" type="text/javascript"></script><script src="//s3-eu-west-1.amazonaws.com/alpha.neohq.net/docs/new-manual/assets/search.js" type="text/javascript"></script><meta name="generator" content="DocBook XSL Stylesheets V1.79.1"></meta>
      <link rel="prev" href="../pagerank/" title="18.4.&nbsp;PageRank Algorithm"></link>
      <link rel="shortcut icon" href="https://neo4j.com/wp-content/themes/neo4jweb/favicon.ico"></link><script>
        $(document).ready(function() {
          CodeMirror.colorize();
          tabTheSource($('body'));
          var $header = $('header').first();
          $header.prepend(
            $('<a href="" id="logo"><img src="https://neo4j.com/wp-content/themes/neo4jweb/assets/images/neo4j-logo-2015.png" alt="Neo4j Logo"></img></a>')
          );
          var $sidebar = $('<div id="sidebar-wrapper"></div>');
          $.get('toc.html', function (d){
            $(d).appendTo($sidebar);
            highlightToc();
            highlightLibraryHeader();
          });
          $sidebar.insertAfter($('header').first());
        });
        </script></head>
   <body>
      <header>
         <div class="searchbox">
            <form id="search-form" class="search" name="search-form" role="search"><input id="search-form-input" name="q" title="search" type="search" lang="en" placeholder="Search Neo4j docs..." aria-label="Search Neo4j documentation" max-length="128" required="required"></input><input id="search-form-button" type="submit" value="Search"></input></form>
         </div>
         <ul class="documentation-library">
            <li><a href="https://neo4j.com/docs/operations-manual/current">Operations Manual</a></li>
            <li><a href="https://neo4j.com/docs/developer-manual/current/">Developer Manual</a></li>
            <li><a href="https://neo4j.com/docs/ogm-manual/current/">OGM Manual</a></li>
            <li><a href="https://neo4j.com/docs/graph-algorithms/current/">Graph Algorithms</a></li>
            <li><a href="https://neo4j-contrib.github.io/neo4j-apoc-procedures/3.4/">APOC</a></li>
            <li><a href="https://neo4j.com/docs/java-reference/current/">Java Reference</a></li>
         </ul>
         <nav id="header-nav"><span class="nav-previous"><a accesskey="p" href="../pagerank/"><span class="fa fa-long-arrow-left" aria-hidden="true"></span>PageRank Algorithm</a></span><span class="nav-current">
               <p class="nav-title hidden">18.3.&nbsp;Centrality Algorithms</p></span><span class="nav-next"></span></nav>
      </header>
      <div id="search-results" class="hidden"></div>
      <section class="section" id="centrality">
         <div class="titlepage">
            <div>
               <div>
                  <h2 class="title" style="clear: both"><a class="anchor" href="#centrality"></a>18.3.&nbsp;Centrality Algorithms
                  </h2>
               </div>
            </div>
         </div>
         <div class="admonitionblock warning">
            <table>
               <tbody>
                  <tr>
                     <td class="icon"><i class="fa icon-warning" title="warning"></i></td>
                     <td class="content">
                        <p>Graph Algorithms (similarity, centrality and clustering) in APOC are deprecated and about to be removed.
                           Please use the algorithms in <a class="link" href="https://r.neo4j.com/algo" target="_top">neo4j-graph-algorithms</a> instead.
                        </p>
                     </td>
                  </tr>
               </tbody>
            </table>
         </div>
         <section class="section" id="_setup">
            <div class="titlepage">
               <div>
                  <div>
                     <h3 class="title"><a class="anchor" href="#_setup"></a>18.3.1.&nbsp;Setup
                     </h3>
                  </div>
               </div>
            </div>
            <p>Let&#8217;s create some test data to run the Centrality algorithms on.</p><pre class="programlisting highlight"><code data-lang="cypher">// create 100 nodes
FOREACH (id IN range(0,1000) | CREATE (:Node {id:id}))

// over the cross product (1M) create 100.000 relationships
MATCH (n1:Node),(n2:Node) WITH n1,n2 LIMIT 1000000 WHERE rand() &lt; 0.1

CREATE (n1)-[:TYPE]-&gt;(n2)</code></pre></section>
         <section class="section" id="_closeness_centrality_procedure">
            <div class="titlepage">
               <div>
                  <div>
                     <h3 class="title"><a class="anchor" href="#_closeness_centrality_procedure"></a>18.3.2.&nbsp;Closeness Centrality Procedure
                     </h3>
                  </div>
               </div>
            </div>
            <p>Centrality is an indicator of a node&#8217;s influence in a graph. In graphs there is a natural distance metric between pairs of
               nodes, defined by the length of their shortest paths.
               For both algorithms below we can measure based upon the direction of the relationship, whereby the 3rd argument represents
               the direction
               and can be of value BOTH, INCOMING, OUTGOING.
            </p>
            <p>Closeness Centrality defines the farness of a node as the sum of its distances from all other nodes, and its closeness as
               the reciprocal of farness.
            </p>
            <p>The more central a node is the lower its total distance from all other nodes.</p>
            <p>Complexity: This procedure uses a BFS shortest path algorithm. With BFS the complexes becomes <code class="literal">O(n * m)</code>
               Caution: Due to the complexity of this algorithm it is recommended to run it on only the nodes you are interested in.
            </p><pre class="programlisting highlight"><code data-lang="cypher">MATCH (node:Node)
WHERE node.id %2 = 0
WITH collect(node) AS nodes
CALL apoc.algo.closeness(['TYPE'],nodes,'INCOMING') YIELD node, score
RETURN node, score
ORDER BY score DESC</code></pre></section>
         <section class="section" id="_betweenness_centrality_procedure">
            <div class="titlepage">
               <div>
                  <div>
                     <h3 class="title"><a class="anchor" href="#_betweenness_centrality_procedure"></a>18.3.3.&nbsp;Betweenness Centrality Procedure
                     </h3>
                  </div>
               </div>
            </div>
            <p>The procedure will compute betweenness centrality as defined by Linton C. Freeman (1977) using the algorithm by Ulrik Brandes
               (2001).
               Centrality is an indicator of a node&#8217;s influence in a graph.
            </p>
            <p>Betweenness Centrality is equal to the number of shortest paths from all nodes to all others that pass through that node.</p>
            <p>High centrality suggests a large influence on the transfer of items through the graph.</p>
            <p>Centrality is applicable to numerous domains, including: social networks, biology, transport and scientific cooperation.</p>
            <p>Complexity: This procedure uses a BFS shortest path algorithm. With BFS the complexes becomes O(n * m)
               Caution: Due to the complexity of this algorithm it is recommended to run it on only the nodes you are interested in.
            </p><pre class="programlisting highlight"><code data-lang="cypher">MATCH (node:Node)
WHERE node.id %2 = 0
WITH collect(node) AS nodes
CALL apoc.algo.betweenness(['TYPE'],nodes,'BOTH') YIELD node, score
RETURN node, score
ORDER BY score DESC</code></pre></section>
      </section>
      <footer><script type="text/javascript">
          (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
            (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
          m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
          })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
          //Allow Linker
          ga('create', 'UA-1192232-34','auto', {'allowLinker': true});
          ga('send', 'pageview');
          // Load the plugin.
          ga('require', 'linker');
          // Define which domains to autoLink.
          ga('linker:autoLink', ['neo4j.org','neo4j.com','neotechnology.com','graphdatabases.com','graphconnect.com']);
        </script><script type="text/javascript">
          document.write(unescape("%3Cscript src='//munchkin.marketo.net/munchkin.js' type='text/javascript'%3E%3C/script%3E"));
        </script><script>Munchkin.init('773-GON-065');</script></footer>
   </body>
</html>